/// https://leetcode-cn.com/problems/valid-sudoku
pub struct Solution;

impl Solution {
    /// 执行用时： 0 ms , 在所有 Rust 提交中击败了 100.00% 的用户
    /// 内存消耗： 2 MB , 在所有 Rust 提交中击败了 44.68% 的用户
    /// 使用数组来对 HashSet 改进；还可以继续改进：把三个数组降成一个数组，参考
    /// https://leetcode-cn.com/problems/valid-sudoku/solution/you-xiao-de-shu-du-by-leetcode/300864
    pub fn is_valid_sudoku(board: Vec<Vec<char>>) -> bool {
        // row: 第一层代表第 1-9 数字，第二层代表第 1-9 行；col、 block 类似
        let [mut row, mut col, mut block] = [[[0u8; 9]; 9]; 3];
        let exists = |arr: &mut [[u8; 9]; 9], number: usize, idx: usize| -> bool {
            arr[number][idx] += 1;
            return if arr[number][idx] > 1 { true } else { false };
        };
        for i in 0..9 {
            for j in 0..9 {
                let ch = board[i][j];
                if ch != '.' {
                    let number = ch as usize - 49; // '1' 转换 u8 为 49
                    if exists(&mut row, number, i)
                       || exists(&mut col, number, j)
                       || exists(&mut block, number, i / 3 * 3 + j / 3)
                    {
                        return false;
                    }
                }
            }
        }
        true
    }

    /// 执行用时： 4 ms , 在所有 Rust 提交中击败了 97.87% 的用户
    /// 内存消耗： 2.1 MB , 在所有 Rust 提交中击败了 25.53% 的用户
    pub fn is_valid_sudoku1(board: Vec<Vec<char>>) -> bool {
        let mut row = vec![std::collections::HashSet::new(); 9];
        let (mut col, mut block) = (row.clone(), row.clone());
        for i in 0..9 {
            for j in 0..9 {
                let c = board[i][j];
                if c != '.'
                   && (!row[i].insert(c)
                       || !col[j].insert(c)
                       || !block[i / 3 * 3 + j / 3].insert(c))
                {
                    return false;
                }
            }
        }
        true
    }

    /// 执行用时： 4 ms , 在所有 Rust 提交中击败了 97.87% 的用户
    /// 内存消耗： 1.9 MB , 在所有 Rust 提交中击败了 93.62% 的用户
    pub fn is_valid_sudoku2(board: Vec<Vec<char>>) -> bool {
        let mut set = std::collections::HashSet::new();
        let mut set2 = set.clone();
        // row || column
        for i in 0..9 {
            set.clear();
            set2.clear();
            for j in 0..9 {
                if (board[i][j] != '.' && !set.insert(board[i][j]))
                   || (board[j][i] != '.' && !set2.insert(board[j][i]))
                {
                    return false;
                }
            }
        }
        // 3*3 square
        for i in (0..9).step_by(3) {
            for j in (0..9).step_by(3) {
                set.clear();
                for ii in 0..3 {
                    for jj in 0..3 {
                        if board[i + ii][j + jj] != '.' && !set.insert(board[i + ii][j + jj]) {
                            return false;
                        }
                    }
                }
            }
        }
        true
    }

    /// 执行用时： 4 ms , 在所有 Rust 提交中击败了 97.87% 的用户
    /// 内存消耗： 1.9 MB , 在所有 Rust 提交中击败了 97.87% 的用户
    pub fn is_valid_sudoku3(board: Vec<Vec<char>>) -> bool {
        let mut set = std::collections::HashSet::new();
        // row
        for v in &board {
            set.clear();
            for ch in v {
                if *ch != '.' && !set.insert(*ch) {
                    return false;
                }
            }
        }
        // column
        for i in 0..9 {
            set.clear();
            for j in 0..9 {
                if board[j][i] != '.' && !set.insert(board[j][i]) {
                    return false;
                }
            }
        }
        // 3*3 square
        for i in (0..9).step_by(3) {
            for j in (0..9).step_by(3) {
                set.clear();
                for ii in 0..3 {
                    for jj in 0..3 {
                        if board[i + ii][j + jj] != '.' && !set.insert(board[i + ii][j + jj]) {
                            return false;
                        }
                    }
                }
            }
        }
        true
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn assert(f: impl Fn(Vec<Vec<char>>) -> bool) {
        let v = vec![vec!['5', '3', '.', '.', '7', '.', '.', '.', '.'],
                     vec!['6', '.', '.', '1', '9', '5', '.', '.', '.'],
                     vec!['.', '9', '8', '.', '.', '.', '.', '6', '.'],
                     vec!['8', '.', '.', '.', '6', '.', '.', '.', '3'],
                     vec!['4', '.', '.', '8', '.', '3', '.', '.', '1'],
                     vec!['7', '.', '.', '.', '2', '.', '.', '.', '6'],
                     vec!['.', '6', '.', '.', '.', '.', '2', '8', '.'],
                     vec!['.', '.', '.', '4', '1', '9', '.', '.', '5'],
                     vec!['.', '.', '.', '.', '8', '.', '.', '7', '9']];
        assert_eq!(f(v), true);
        let v = vec![vec!['8', '3', '.', '.', '7', '.', '.', '.', '.'],
                     vec!['6', '.', '.', '1', '9', '5', '.', '.', '.'],
                     vec!['.', '9', '8', '.', '.', '.', '.', '6', '.'],
                     vec!['8', '.', '.', '.', '6', '.', '.', '.', '3'],
                     vec!['4', '.', '.', '8', '.', '3', '.', '.', '1'],
                     vec!['7', '.', '.', '.', '2', '.', '.', '.', '6'],
                     vec!['.', '6', '.', '.', '.', '.', '2', '8', '.'],
                     vec!['.', '.', '.', '4', '1', '9', '.', '.', '5'],
                     vec!['.', '.', '.', '.', '8', '.', '.', '7', '9']];
        assert_eq!(f(v), false);
        let v = vec![vec!['.', '.', '.', '.', '5', '.', '.', '1', '.'],
                     vec!['.', '4', '.', '3', '.', '.', '.', '.', '.'],
                     vec!['.', '.', '.', '.', '.', '3', '.', '.', '1'],
                     vec!['8', '.', '.', '.', '.', '.', '.', '2', '.'],
                     vec!['.', '.', '2', '.', '7', '.', '.', '.', '.'],
                     vec!['.', '1', '5', '.', '.', '.', '.', '.', '.'],
                     vec!['.', '.', '.', '.', '.', '2', '.', '.', '.'],
                     vec!['.', '2', '.', '9', '.', '.', '.', '.', '.'],
                     vec!['.', '.', '4', '.', '.', '.', '.', '.', '.']];
        assert_eq!(f(v), false);
        let v = vec![vec!['.', '.', '4', '.', '.', '.', '6', '3', '.'],
                     vec!['.', '.', '.', '.', '.', '.', '.', '.', '.'],
                     vec!['5', '.', '.', '.', '.', '.', '.', '9', '.'],
                     vec!['.', '.', '.', '5', '6', '.', '.', '.', '.'],
                     vec!['4', '.', '3', '.', '.', '.', '.', '.', '1'],
                     vec!['.', '.', '.', '7', '.', '.', '.', '.', '.'],
                     vec!['.', '.', '.', '5', '.', '.', '.', '.', '.'],
                     vec!['.', '.', '.', '.', '.', '.', '.', '.', '.'],
                     vec!['.', '.', '.', '.', '.', '.', '.', '.', '.']];
        assert_eq!(f(v), false);
    }

    // is_valid_sudoku:  1,361  ns/iter (+/- 96)
    // is_valid_sudoku1: 13,063 ns/iter (+/- 7,303)
    // is_valid_sudoku2: 7,137  ns/iter (+/- 170)
    // is_valid_sudoku3: 8,415  ns/iter (+/- 431)
    bench!(assert Solution::is_valid_sudoku);
    bench!(assert Solution::is_valid_sudoku1);
    bench!(assert Solution::is_valid_sudoku2);
    bench!(assert Solution::is_valid_sudoku3);
}
